﻿#define _CRT_SECURE_NO_WARNINGS 1

#include"Sort.h"

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


//排序 - 升序
//插入排序 直接插入排序 希尔排序
void insertSort(int* a, int n)
{
	//将前面的一个一个进行比较，找到待插入数据应该放的位置
	//外部的控制的循环
	for (int i = 0; i < n -1; i++)//将只有一个数据䣌序列当作有序序列;有n个数据只需要比较n-1次
	{
		int end = i;
		int key = a[end + 1];
		while (end >= 0)
		{
			if (key < a[end])
			{
				a[end + 1] = a[end];
				end -= 1;
			}
			else
			{
				break;
			}
		}
		//出了循环便可以放key 
		a[end + 1] = key;
	}
}
//希尔排序
//希尔排序是对直接插入排序的升级
//让排在前面的大数据快速跳转到后面去，让排在前面的小数据快速地跳转到前面去
void ShellSort(int* a, int n)
{
	//gap 的思想，让距离均为gap 的数据划分为一组
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3;
		// i+gap < n --> i<n-gap
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int key = a[end + gap];
			while (end >= 0)
			{
				if (key < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			//出了循环便可以放Key
			a[end + gap] = key;
		}

	}
}

//x选择排序 直接选择排序 堆排序
//直接选择排序
//会利用到两个指针，一个在前面，一个在后后
//然后会利用到两个变量寻找待排序序列中的最大值以及最小值
void SelectSort(int* a, int n)
{
	//两个变量找最大以及最小的值
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin + 1; i <= end; i++)//待排序数据的范围
		{
			//找最小
			if (a[i] < a[mini])
			{
				//Swap(&a[i], &a[mini]); 不应该是交换，应该是记录下标
				mini = i;
			}
			//最大
			if (a[i] > a[maxi])
			{
				//Swap(&a[i], &a[maxi]);
				maxi = i;
			}
		}
		//将在待排序列中找到的最大值最小值，放到他们应该存放的位置上去 交换
		Swap(&a[begin], & a[mini]);
		//存在特殊需要单独处理的情况，此时需要额外判断一下
		if (maxi == begin)//判断的== 写成了 = ！！！！
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		//调整begin  end
		begin++;
		end--;
	}
}
//堆排序
//堆排序会借助到堆这个数据结构的思想
//可以是向下调整建堆，也可以是向上调整建堆
//排升序， 建大堆；排降序，建小堆
//此处排升序 - 大堆
//向上调整 - 大堆
void AdjustUp(int* a, int child)
{
	//从下向上进行调整
	//可以利用孩子节点得到父节点的下标
	int parent = (child - 1) / 2;
	//然后让子节点与其父节点进行比较
	while(parent >= 0)
	{
		//大堆 ： 父节点>= 子节点
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			//迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整建堆
//从最后一个非叶节点开始进行调整
//叶节点便可以看作一个堆
void AdjustDown(int* a, int parent, int n)
{
	//假设法 - 大堆 - 父节点要与其较大的子节点进行比较
	//该父节点可能有两个子节点，也有可能由有一个子节点甚至没有子节点
	//子节点有无的判断是依据下标的计算，利用父节点的下标计算其子节点的下标，看其子节点的下标是否在数组下标的合理范围内
	int child = parent * 2 + 1;//假设为左子节点

	while (child < n)//子节点的下标在数组合理的范围中，即该父节点有子节点
	{
		//假设法，如果存在右孩子，就需要将左孩子中的值与右孩子的数值进行比较取其较大值
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child += 1;
		}
		//父节点与其较大子节点之间的比较
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//调试6666
		}
	}

}
void HeapSort(int* a, int n)
{
	//向上调整建堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}
	//向下调整建堆 - 从最后一个非叶节点开始
	/*for(int i = (n - 1  - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}*/
	//堆排序 - 大堆 - 将大数据放在后面
	int sz = n - 1;//实际会调整的次数
	while (sz)
	{
		//将堆顶的数据与最后一个数据进行交换
		Swap(&a[0], &a[sz]);
		//向下调整 ， 对堆根中的数据
		AdjustDown(a, 0, sz);
		sz--;
	}
}

//交换排序 - 冒泡排序 快速排序
//冒泡排序
void BubbleSort(int* a, int n)
{
	//首先是控制冒泡的趟数，有n个数据就需要冒泡n-1 次
	for (int i = 0; i < n - 1; i++)
	{
		//控制每次冒泡需要比较的数据的个数，每次走完一趟冒泡便会确定一个数据的位置
		//故而每趟所要比较的数据是有变化的
		int flag = 1;
		for (int j = 0; j < n - 1 - i; j++)
		{
			//升序 前一个大于后一个便交换
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;//本身就是有序便不用再继续
		}
	}
}
//快速排序
//hoare 版本
//快速排序的核心思想就是利用两个指针，一个从左往右找大于基准值的数据，一个从右往左找小于基准值的数据
//当Left 和right 均再合理范围的时候便可以进行交换
//挖坑版本
//先将坑放在最左，将坑中的数据计为key；先让right 从右往左找小于基准值的数据，找到之后，便可以让right中的数据放在hole 之中
// 然后将坑位移动到right 之下；left 从左往右找大于基准值的数据……
//lomuto - 前后指针版本
//会利用到两个指针，从前往后找小于基准值的数据，找到了便放在Prev 所指向的下一空间的数据，prev 负责指向小于基准值数据的尾数据

//优化 ： 三数取中
int GetMid(int* a, int left, int right)
{
	//利用left 与right 求得中间值
	int mid = (left + right) / 2;
	//比较谁是中间值
	if (a[left] < a[right])
	{
		// left  right
		if (a[mid] < a[left])
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}
	else
	{
		//   right  left
		if (a[mid] < a[right])
			return right;
		else if (a[mid] > a[left])
			return left;
		else
			return mid;
	}
}


//hoare 版本
//利用两个指针
int _QuickSort1(int* a, int left, int right)
{
	//int keyi = left;
	//利用三数取中得到基准值
	int keyi = GetMid(a, left, right);
	//将keyi 中的内容与left 中的内容进行交换
	if (keyi != left)
	{
		Swap(&a[keyi], &a[left]);
	}
	left++;
	while (left <= right)
	{
		//让right 从右往左找小于基准值得数据
		while (left <= right && a[right] >= a[keyi])
		{
			right--;
		}
		//让left 从左往右找大于基准值的数据
		while (left <= right && a[left] <= a[keyi])
		{
			left++;
		}
		//当left  与 right 均在合理的范围的时候才会发生交换
		if (left <= right)
		{
			Swap(&a[left], &a[right]);
		}
	}
	//出了循环便代表left > right 
	//right 的右边全是大于基准值的数据
	//由于是right 先走，越界有两种情况，right 越界，那么right的右边不包含自己均是大与基准值的数据，此时keyi 和 right 中的数据进行交换便可
	//二是left 越界，那么left的右边不包含left 均是小于基准值的数据,此时keyi 与 right 进行交换便可
	Swap(&a[keyi], &a[right]);
	return right;
}

//挖坑法
int _QuickSort2(int* a, int left, int right)
{
	//默认让坑位为最左的，并且利用变量将基准值保存起来
	//int key = a[left];
	//利用三数取中获得基准值
	int keyi = GetMid(a, left, right);
	//将left 中的数据与keyi 中的数据进行交换
	Swap(&a[left], &a[keyi]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//让right 从右往左找小于基准值的数据
		while (left < right && a[right] >= key)
		{
			right--;
		}
		//将right 中的数据放到坑中，并且坑位需要移动
		a[hole] = a[right];
		hole = right;
		//让left 从左往右找大于基准值的数据
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	//当出了循环便代表着left == right
	//此时坑位在left 与 right 指向的空间中
	//最后将基准值放到坑位中即可
	a[hole] = key;
	return hole;
}
//lomuto 前后指针法
int _QuickSort3(int* a, int left, int right)
{
	//将最左值当作基准值的下标
	//int keyi = left;
	//利用三数取中获得基准值下标
	int keyi = GetMid(a, left, right);
	//将keyi 中的数据与最左值进行交换
	if (keyi != left)
	{
		Swap(&a[left], &a[keyi]);
	}
	keyi = left;
	int prev = left, cur = left+1;//调试精神！！！！！！！！！！！！！！！！！！！！！！！
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		//cur 需要迭代往前走
		cur++;
	}
	//prev 始终指向小于基准值的尾数据的位置
	//所以prev 与 keyi 中的数据进行就可以了
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	//利用递归的思想，不断地确定基准值的位置
	//递归的条件：范围合理以及序列中待排序的数据个数大于等于2
	if (left >= right)
		return;

	//相当于先序遍历
	//hoare 版本
	//int keyi = _QuickSort1(a, left, right);
	//挖坑法
	//int keyi = _QuickSort2(a, left, right);
	// lomuto 前后指针
	int keyi = _QuickSort3(a, left, right);

	//再根据基准值的下标划分区域
	//left,keyi-1 keyi keyi+1, right
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

//归并排序
//归并排序 - 相当于树的后序遍历
//将两个有序的数组进行比较合并
void _MergeSort(int* a, int* tmp, int left, int right)
{
	if (left >= right)
		return;

	//利用mid 将待排序序列进行分割
	int mid = (left + right) / 2;
	//left,mid  mid+1,right
	_MergeSort(a, tmp, left, mid);
	_MergeSort(a, tmp, mid +1 , right);
	//合并两个有序的数组
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	//int index = 0;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	//剩下的数据
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}

	//将tmp 中的数据拷贝放回left 到right 的范围之中
	/*int i = 0;
	for (int j = left; j <= right; j++)
	{
		a[j] = tmp[i++];
	}*/
	//也可以使用memcpy
	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{
	//动态开辟数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	_MergeSort(a, tmp, 0, n - 1);
	//释放
	free(tmp);
	tmp = NULL;
}